//
// Created by Administrator on 2021/5/6.
//
/*

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，
 所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

你需要原地修改栈。

示例1:

输入：A = [2, 1, 0], B = [], C = []
输出：C = [2, 1, 0]
示例2:

输入：A = [1, 0], B = [], C = []
输出：C = [1, 0]
提示:

A中盘子的数目不大于14个。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hanota-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

#include <iostream>
#include <vector>

using namespace std;

void towerOfHanoi(int n, int x, int y, int z) { // hanoi 递归方案
    // 把塔x顶部的n个碟子转移到塔y , 用塔z作为中转
    if (n > 0) {
        // 拆分为两步
        towerOfHanoi(n - 1, x, z, y);  // 把n-1个碟子从x移动到z，借助y
        cout << "Move top disk from tower " << x << " to top of tower " << y << endl; // 将x底部的盘子移动到y
        towerOfHanoi(n - 1, z, y, x);  // 把n-1个碟子从z移动到y，借助x
    }
}

class Solution {
public:
    void hanota(vector<int> &A, vector<int> &B, vector<int> &C) {
        // 这里是用vector数组模拟栈
        hanoiMove((int)A.size(),A,C,B);
    }
    void hanoiMove(int n,vector<int> &T1, vector<int> &T2, vector<int> &T3){
        if (n>0){
            hanoiMove(n-1,T1,T3,T2); // 把n-1个碟子从A移动到C，借助B
            T2.push_back(T1.back());   // 将A底部的盘子移动到B
            T1.pop_back();
            hanoiMove(n-1,T3,T2,T1); // 把n-1个碟子从C移动到B，借助A
        }
    }

};

int main() {
//    towerOfHanoi(5, 1, 2, 3);
    vector<int> t1{2, 1, 0};
    vector<int> t2{};
    vector<int> t3{};
    Solution solution;
    solution.hanota(t1, t2, t3);
    for (auto x:t3) cout << x << endl;
    return 0;
}